MySQL Index Introduction

谈谈数据库

事务与ACID其实是为了帮程序员屏蔽底层并发的细节.

ACID Vs CAP

note:

• 顺序一致性:所有处理器的内存访问是交叉的,然而程序的行为好像它们是按顺序执行的
• 原子/线性一致性:顺序一致性+实时约束.线性一致性假设所有处理器共享全局时间
• Isolation
  • serializable可序列化:读写均锁表,强行单线程操作....开发人员可以躺平了
  • repeatable read:事务开始时建立一致性视图,读取时若DB_TRX_ID(处理的事务数ID)在视图建立前未提交,则读到的是原来的数据(多版本并发MVCC的基础)
  • read committed读取已提交数据:写的时候锁行,写完了commit再允许被读
  • read uncommitted读取未提交数据:什么也不做,只要内存中改了记录就能被读
• Base理论，基本可用->最终一致性

对数据库的操作依然离不开查找和排序，并且传承于通用的数据结构与算法。

2. 对传统索引的理解

2.1. 只是支持快速查找的数据结构

索引的本质在查询关键字与数据库记录之间建立的一种支持快速查找的数据结构 ，不一定是b+树，也可以是hash索引，也可以是b树/二叉树/数组/n叉树等等。
因为磁盘相比主存慢十万倍，而且磁盘一次能取一个扇区的数据¹，因此索引的设计应当使每次磁盘I/O取到内存的数据都能帮助后续记录的定位，尽可能减少IO的次数。以第二行做二叉树形式的索引结构如下：

• B树（多路平衡二叉树）俯视图²：

• B+树只是一种均衡各方面的产物：

B+树正面图：

2.2. 索引的演化简史

• 索引结构经历了Hash -> 二叉树 -> 平衡二叉树（BST） -> 多路平衡二叉树（B-Tree） -> B+树 -> B*树的演变过程，依次提供了一些功能或解决了一些问题：
  • 直接给每个记录唯一的键(hash值)，并通过唯一键给记录定位是最直接的想法
    • 不同索引键可能存在相同 Hash 值而碰撞，且不支持Key比较，且不支持范围遍历
  • 支持范围查找O(log2n)
    • 树结点因为包括<指针，主键，(记录)）>所需空间变大
  • 分叉少容易树高则查找次数变多
  • 支持n叉，尽可能在3次IO内定位记录，充分利用每次磁盘I/O取到内存的索引(每一次取的数据包含下一次的索引)
  • 受限于每一个数据页（结点）的存储空间16k(InnoDB),分开存储各级索引与记录以便每层存储更多索引，降低树深
    • 层数可以不变，但是能存储的更多了.假设每个结点大小为2k,结点中每一个指针为6-8B
    • 第一层1个2k大小的结点 -> 第二层200个结点 -> 第三层200^2 = 40000个结点,这三层大小=2k + 0.4m + 80m,足够三层放入内存中,而第4层可以支撑200^4=16亿条数据,恰好他们也都在磁盘中.这种情况下也只有一次与磁盘的IO
  • 结点必要时换父亲，尽可能减少页分裂的次数
• 红黑树虽然也是B-Tree类型的树，但不会控制树的高度，所以不适合利用磁盘存储的MySQL 的。而因为B-Tree每一块的大小是固定的，如果有新的元素处于一个满了数据块的范围内，则会触发该数据块分裂,最糟糕时情况是一次插入操作所有的数据块都分裂了一遍，则带来的问题就是存储浪费，所以它不适合内存

2.3. 索引聚不聚簇

以新华字典为例说明，新华字典提供主要的索引方法：拼音查询。因为字典本身按照这样的索引已聚集排序，当输入一个拼音如gong--一个Key,就可以按照g--ong（--笔画数）不断缩小查找范围，最后遍历最小的那个分类集合命中汉字--一个value.这样像拼音这样的索引被称作”聚簇索引(Clustered Index)“。聚簇索引本身并不需要聚簇索引表。
可以看出聚簇索引并不是一种单独的索引类型，而是一种数据存储方式，满足聚簇的字面意思³。必须注意的是，每张表有且仅有一个聚簇索引,⁴因为数据库只能按照一种方法进行排序。

同时字典也提供部首查询的方法，字典中字排列顺序与这里索引--部首的排序不一致，所以部首查询表本身一定需要包含命中的指向字的直接索引。有过部首查询经历会发现，部首查询表自己是按笔画数进行的划分，先按照”一笔“”二笔“”三笔“...这样类似数组下标的索引查得部首如"工"，接着同样按照笔画数如三笔--一个Key,又查到部首索引表中的字与它对应的页数--一个<K,V>,而这里的V是一个指向实际物理文件--字典中字的point.这里的部首索引表本身也就是一个含有笔画--这种聚簇索引的表，而对于字典，部首索引表的部首则是”非聚簇索引（Noinclustered Index）“

新华字典的层级关系可以表示为

假设每页为一记录，自然地页数就是主键id,并且满足主键约束（不重复）。在页数之上添加的部首索引表便是在聚簇索引的基础上添加了非聚簇索引。
而在数据库中，索引是通过n叉树的形式进行描述的。承接上述的层级关系，聚簇索引的叶子结点是最终的数据结点记录，而非聚簇索引的叶子结点仍然是索引节点，一定有一个指向最终数据的指针。

对于使用聚簇索引方式存储的表,每个索引后都会附加索引信息?

2.4. 索引优缺点⁶

2.4.1. 优点

1. 索引大大减少了存储引擎需要扫描的数据量。因为可以逐步聚焦需要的记录。

2. 索引可以帮助存储引擎避免排序和临时表。因为对于聚簇索引本身记录会按索引组织，从而也可以避免临时表之后再建立索引。

3. 索引可以将随机 I/O 变成顺序 I/O（比如B+树底部的双链表）。随机指的是无目的查询，相比有了索引关键字，只需要按步骤顺序查询或者遍历叶节点就好。

2.4.2. 缺点

1. 降低更新表的速度，如对表进行 INSERT、UPDATE 和 DELETE。因为更新表时，MySQL 不仅要更新数据，还要更新索引文件。

2. 索引文件会占用磁盘空间。当在一个大表上创建了多种组合索引，且伴随大量数据量插入，索引文件大小也会快速膨胀。

3. 在重复列上添加聚簇索引，引擎需要自动添加额外字段以组合满足主键（PRIMARY KEY）UNIQUE约束。因此对于包含重复的内容的数据列，是否建立聚簇与非聚簇索引得综合判断⁵。

4. • 如果是性别标签“男 女 未知”这种对应的大量重复记录，索引开销可能大于直接遍历；

   • 如果是日期划分，虽然每日有许多，但是每一个按日的聚合划分仍然有效区分数据集，建立聚簇索引；

   • 小数据集或数据记录本身小，直接排序更好，优先聚簇索引；
   • 如果一条记录本身十分大，为了降低insert的维护开销，可用非聚簇索引（以避免对记录的重排序？）

5. 对于记录很少的表，不仅仅范围查询，大部分情况下简单的全表扫描更高效。因为拿到主索引回表查一次，可能会涉及 I/O 的行数更多,同样这也是聚簇索引优于非聚簇索引，以及select *垃圾的原因。